/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        450.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 22:11
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个二叉搜索树的根节点 root 和一个值 key，
// 删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。
// 返回二叉搜索树（有可能被更新）的根节点的引用。
//
//一般来说，删除节点可分为两个步骤：
//
//首先找到需要删除的节点；
//如果找到了，删除它。
//说明： 要求算法时间复杂度为O(h)，h 为树的高度。
#include "../header.h"

class Solution {
public:
    TreeNode *deleteNode(TreeNode *root, int key) {
        if (root == nullptr)
            return nullptr;
        if (root->val > key)
            root->left = deleteNode(root->left, key);
        else if (root->val < key)
            root->right = deleteNode(root->right, key);
        else {
            if (root->right == nullptr) return root->left;
            if (root->left == nullptr) return root->right;
            TreeNode *min = getMin(root->right);
            root->val = min->val;
            root->right = deleteNode(root->right, min->val);
        }
        return root;
    }

    TreeNode *getMin(TreeNode *root) {
        while (root->left != nullptr)
            root = root->left;
        return root;
    }
};

